package com.mgq.algorithm.link;

import java.util.HashSet;

/**
 * @author MaGuangQi
 * 返回两个相交链表的开始节点
 * @date 2021-12-31 17:21
 **/
public class IntersectionLinkedList_160 {

    /**
     * 直接使用hashSet.把A全部加入.时间复杂度是O(N),空间复杂度O(N)
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> hashSet = new HashSet<>();
        //把A全部加入到hash表中
        while (headA != null) {
            hashSet.add(headA);
            headA=headA.next;
        }
        //hash表和链表B比较.内存地址一样,就是相交的节点
        while (headB != null) {
            if (hashSet.contains(headB)) {
                return headB;
            }
            headB=headB.next;
        }
        return null;
    }

    /**
     *a1->a2->a3
     *          \
     *            c1->c2
     *          /
     *    b2->b3
     * 思路:先遍历a链表,再遍历b链表
     * a1,a2,a3,c1,c2,b2,b3,c1,c2
     * b2,b3,c1,c2,a1,a2,a3,c1,c2
     *                      c1 公共部分
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode p1=headA;
        ListNode p2=headB;
        while (p1 != p2) {
            if (p1 != null) {
                // p1 走一步，如果走到 A 链表末尾，转到 B 链表
                p1 = p1.next;
            } else {
                p1=headB;
            }

            if (p2 != null) {
                // p2 走一步，如果走到 B 链表末尾，转到 A 链表
                p2 = p2.next;
            } else {
                p2=headA;
            }
        }
        //返回p1,p2都行
        return p2;
    }

    /**
     * 思路3:首先让两个链表都走完,因为题目保证链表没有环,所以一定可以走完
     * 当2个链表走完时,我们看最后的节点值.分2种情况
     * 情况1: 2个节点不相等,表示不是同一节点,此时表示链表没有相交,返回null即可
     * 情况2:2个节点的值相等,表示是同一节点,此时链表有相交节点.
     * 如何返回相交的节点呢:
     *       遍历的时候记录链表的长度. 取2个链表长度的差值.
     *       让链表最长的链表先走差值步,然后2个链表同时在走,此时再相遇时,就是2个相交链表的第一个节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        int length1=0;
        int length2=0;
        ListNode cur1=headA;
        ListNode cur2=headB;
        //这样不会走到null,只会到最后一个节点
        while (cur1.next != null) {
            length1++;
            cur1=cur1.next;
        }
        while (cur2.next != null) {
            length2++;
            cur2 = cur2.next;
        }
        //表示没有相交
        if (cur1 != cur2) {
            return  null;
        }
        //相交了.找出长度最大的链表
         cur1 = length1 > length2 ? headA : headB;
         cur2 = cur1 == headA ? headB : headA;
        int n = Math.abs(length1 - length2);
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1=cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}
